COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	Is 1729 an interesting number?  Yes, according to Ramanujan ("Rom-uh-NOO-jun"):
C00009 ENDMK
C⊗;
Is 1729 an interesting number?  Yes, according to Ramanujan ("Rom-uh-NOO-jun"):
it is the smallest number that you can get by adding two perfect cubes in two
different ways.


	10↑3  + 9↑3  = 1000 + 729 = 1729

	12↑3  + 1↑3  = 1728 +   1 = 1729

We will develop an algorithm to find, in increasing order, any other such
``interesting'' numbers up to a million.

Method 1: let  N  be a candidate for ``interesting.''  Iterate  N  from 1 to 
1 000 000.  Within this iteration, iterate  A,B,C,D  from 1 to 100, and print

the variables if A↑3  + B↑3  = C↑3  + D↑3  = N, and A≠C,A≠D.  
Unfortunately, the number of times we execute the inner iteration is  
10↑6  x (100)↑4  = 10↑{14}; at 10↑5  executions per second, 
it will take 31.7 years.

Method 2: just iterate A,B,C,D from 1 to 100, printing if A↑3 + B↑3 = C↑3 + D↑3
and A≠C,A≠D.  Now the program only needs 17 minutes for its 10↑8 iterations, but
the numbers don't come out in increasing order.  Besides, we can do it much faster
by other algorithms.

Method 3: Iterate  A  and  B  from 1 to 100, entering the value of A↑3 + B↑3 into
a table, and printing if the value is already there.  The program only needs 10↑6
operations, but still gives the results in the wrong order, and needs a huge table,
larger than many computer memories.

Method 4: We imagine the numbers that are the sums of two cubes arranged in a
hundred lists; the seventeenth list would contain  
17↑3 + 1, 17↑3 + 8, etc., through 17↑3 + 17↑3.  (Naturally, 17↑3 + 18↑3 appears 
on the eighteenth list, so we don't need it on the seventeenth).  We will move
simultaneously through all the lists, always looking at only one number from
each list.  If a number is smaller than all the others, we replace it by the
next one on its list.  We keep the current numbers in a sorted table, so the
first entry is always the smallest.  If the first entry is equal to the second,
we have found an interesting number.

Let's watch the algorithm in action for a moment.  It has just passed the
number 1000.  The first seven lists are already exhausted.  No number
from the eleventh list has been reached yet, so there is no use looking at
the twelfth or later lists.  The sorted table looks like this:

	List 10: 10↑3 + 1↑3 = 1001

	List  8:  8↑3 + 8↑3 = 1024

	List  9:  9↑3 + 7↑3 = 1072

	List 11: 11↑3 + 0↑3 = 1331

The algorithm finds that the two entries at the top of the table are different,
so it prints nothing.  It changes the top entry, first to

10↑3 + 2↑3 = 1008, then to 10↑3 + 3↑3 = 1027, moving the entry down in the table:

	List  8:  8↑3 + 8↑3 = 1024

	List 10: 10↑3 + 3↑3 = 1027

	List  9:  9↑3 + 7↑3 = 1072

	List 11: 11↑3 + 0↑3 = 1331

Now the entry from list 8 is the last of its list, so it is deleted.  A little
later, the table is

	List 11: 11↑3 + 0↑3 = 1331

	List 10: 10↑3 + 7↑3 = 1343

	List  9:  9↑3 + 9↑3 = 1458

Having started to use list 11 as indicated by the 0↑3, it is time to start looking
for numbers from List 12, so we add to the table the first number from List 12,
making the table:

	List 11: 11↑3 + 1↑3 = 1332

	List 10: 10↑3 + 7↑3 = 1343

	List  9:  9↑3 + 9↑3 = 1458

	List 12: 12↑3 + 0↑3 = 1728

The number of steps of the algorithm is no more than 500 000; most of the work
comes in inserting each of the 5000 list entries into a table that never has
more than 100 entries.  In a computer program, we would work only with the
numbers from the tables; at the last stage shown above, we would have:

	Subscript	Array	Array	Array
			  A	  B	  C

	    1		  11	  1	1332
	    2		  10	  7	1343
	    3		   9	  9	1458
	    4		  12	  0	1728

Variable
TABLESIZE = 4

Try programming the algorithm.  You will probably need subprograms to insert a
new entry in the table, to delete an entry, and to move the top entry down to
its correct location when it is not the smallest.

The contrast among the methods becomes far greater if you try it for numbers up
to a billion.  Method 1 then needs 10↑{16} seconds, or 317 million years.  Methods
2 and 3 need a substantial fraction of a year.  Method 4 needs about ten seconds.
Methods using a more advanced table arrangement, called a ``heap,'' can gain
another factor of ten or so.